package bishi.day32_5_31;

import java.util.*;

/**
 * @author 是阿秋啊
 * @date 2022/05/31 13:14
 **/
public class fei_bo_naqie {
    public static void main(String[] args) {
        int[] arr = new int[100001];
        arr[1] = 1;
        arr[2] = 2;
        int sb = 0;
        for (int i = 3; i <= 100000; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            if (sb == 0 && arr[i] >= 1000000) {
                sb = i;
            }
            arr[i] %= 1000000;
        }
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            System.out.printf(n < sb ? "%d\n" : "%06d\n", arr[n]);
        }
    }
}